Secret sharing is a technique by which data is transformed into multiple shares so that the original data can be reconstructed by using a certain number of shares or more but none of the original data can be reconstructed by using any number of shares less than the certain number. Some secret sharing schemes impose restrictions on the total number N of shares and the smallest number K(≦N) of shares required for reconstruction and others not.
A typical secret sharing scheme is Shamir's secret sharing scheme (see Non-patent literature 1, for example). In an example of this scheme, shares Si(a)=f(i) (i=1, . . . , N) of a is obtained from a K−1-degree expression f(x), where x is a variable, such that f(0)=a for aεGF(p), where p is a prime, and GF(p) is a finite field of order p. Here, a can be reconstructed from any K different shares because the following relationship holds:
                              a          =                                    f              ⁡                              (                0                )                                      =                                          ∑                                  i                  =                  1                                K                            ⁢                                                f                  ⁡                                      (                                          n                      i                                        )                                                  ·                                                      L                    i                                    ⁡                                      (                    0                    )                                                                                      ⁢                                  ⁢                                            L              i                        ⁡                          (              x              )                                =                                    ∏                                                j                  ≠                  i                                ,                                  j                  =                  1                                            K                        ⁢                                                  ⁢                                          x                -                                  n                  j                                                                              n                  i                                -                                  n                  j                                                                                        [                  Formula          ⁢                                          ⁢          1                ]            where n1, . . . , nK are different integers greater than or equal to 1 and less than or equal to N.
Another type of secret sharing is ramp secret sharing schemes, in which no part of original data can be reconstructed from K−L or less shares, where L is an integer less than K (see Non-patent literature 2, for example). In an example of the schemes, shares Ti(a)=f(i) (i=1, . . . , N) of information a=(a0, a1, . . . , aL-1) (a0, a1, . . . , aL-1εGF(p)) are obtained from a K−1-degree expression f(x)=a0+a1x+ . . . +aL-1xL-1+rLxL+ . . . +rK-1xK-1, where x is a variable, determined from the information a and random numbers rL, . . . , rK-1εGF(p). Then the coefficients a0, a1, . . . , aL-1 of the expression f(x) can be uniquely obtained from K points (ni, f(ni)) (i=1, K), where n1, . . . , nK are different integers greater than or equal to 1 and less than or equal to N. This can be accomplished simply by finding the solutions for a0, a1, . . . , aL-1 in the following matrix, where a0, a1, . . . , aL-1, rL, . . . , rK-1 are variables.
                              (                                                                      f                  ⁡                                      (                                          n                      1                                        )                                                                                                      ⋮                                                                                      f                  ⁡                                      (                                          n                      K                                        )                                                                                )                =                              (                                                                                n                    1                    0                                                                    …                                                                      N                    1                                          K                      -                      1                                                                                                                    ⋮                                                  ⋱                                                  ⋮                                                                                                  n                    K                    0                                                                    …                                                                      N                    K                                          K                      -                      1                                                                                            )                    ⁢                      (                                                                                a                    0                                                                                                ⋮                                                                                                  a                                          L                      -                      1                                                                                                                                        r                    L                                                                                                ⋮                                                                                                  r                                          K                      -                      1                                                                                            )                                              [                  Formula          ⁢                                          ⁢          2                ]            
On the other hand, a multiparty computation scheme, which uses secret sharing as an elemental technology, has been proposed. The multiparty computation is a technique in which each computing entity i (i=1, . . . , N) takes an input of information ai and obtains a particular function value Fi(a1, . . . , aN) without revealing the information ai to the other computing entities. In Shamir's secret sharing scheme described above, shares Si(a+b) of a+b and shares Si(ab) of ab can be obtained from shares Si(a), Si(b) of information a, bεGF(p) without revealing inputs into the computing entities (see Non-patent literature 3). That is, multiparty computations of addition and multiplication are possible using Shamir's secret sharing scheme. Note that secret sharing that satisfies the relationship Si(a)+Si(b)=si(a+b) is called additive homomorphic secret sharing.
Another type of secret sharing is linear secret sharing schemes. The linear secret schemes can be defined as secret sharing in which all of the shares of original data aεGF(p) can be represented by aεGF(p) and a linear combination of random numbers on GF(p). It is known that any linear secret sharing scheme can be extended to multiparty computation (see Non-patent literature 4).